struct general {
	int height, ie_count, oe_count;
	struct general *prev, *next;
};
typedef struct general G_Node;

struct general_list {
	G_Node *head;
};
typedef struct general_list G_List;

struct edge {
	int height, x_left, x_right;
	G_Node *gnode;
	struct edge *prev, *next;
};
typedef struct edge E_Node;

struct edge_list {
	E_Node *head;
};
typedef struct edge_list E_List;

struct frw {
	int bottom, left, right;
	struct frw *next, *prev;
};
typedef struct frw FRW;

struct frw_list {
	FRW *head;
};
typedef struct frw_list F_List;

struct mer {
	int top, bottom, left, right;
	struct mer *next, *prev;
};
typedef struct mer MER;

struct mer_list {
	MER *head;
};
typedef struct mer_list M_List;

G_List *gell	= (G_List *)NULL;
E_List *iell	= (E_List *)NULL;
E_List *oell	= (E_List *)NULL;

G_Node *ghead	= (G_Node *)NULL;
E_Node *iehead 	= (E_Node *)NULL;
E_Node *oehead	= (E_Node *)NULL;
FRW *rwhead		= (FRW *)NULL;

void print_rwll(F_List *rwll) {
	FRW *rw = rwll->head;
	while (rw != NULL) {
		printf("frw bottom:%d left:%d right:%d\n",rw->bottom, rw->left, rw->right);
		rw = rw->next;
	}
}

void print_merll(M_List *merll) {
	MER *m_temp = merll->head;
	int i = 1;
	printf("*****************\n");
	printf("MER List contains\n");
	printf("vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv\n");
	while (m_temp != NULL) {
		printf("MER-%d : %d-%d-%d-%d\n", i++, m_temp->left, m_temp->right, m_temp->bottom, m_temp->top);
		m_temp = m_temp->next;
	}
}

int merll_size(M_List *merll) {
	MER *m_temp = merll->head;
	int m_size = 0;
	while (m_temp != NULL) {
		m_size++;
		m_temp = m_temp->next;
	}
	return m_size;
}

void create_mer(FRW *rw, int height, M_List *merll) {
	MER *m_temp	= merll->head;
	MER *m_new	= NULL;

	if (rw->bottom < height) {
		m_new	= (MER *)malloc(sizeof(MER));

		m_new->top		= height;
		m_new->bottom	= rw->bottom;
		m_new->left		= rw->left;
		m_new->right	= rw->right;
		m_new->next		= NULL;
		m_new->prev		= NULL;

		if (m_temp == NULL) {
			merll->head	= m_new;
		} else {
			while (m_temp->next != NULL) {
                if ((m_temp->top == m_new->top) && (m_temp->bottom == m_new->bottom) && (m_temp->right >= m_new->left) && (m_temp->left <= m_new->right)) {
                    return;
                }
				m_temp	= m_temp->next;
			}
            if ((m_temp->top == m_new->top) && (m_temp->bottom == m_new->bottom) && (m_temp->right >= m_new->left) && (m_temp->left <= m_new->right)) {
                return;
            }
			m_temp->next 	= m_new;
			m_new->prev	= m_temp;
		}
	}
}

int check_frw(int left, int right, F_List *rwll) {
	FRW *temp = rwll->head;
	temp = rwhead;

	while (temp != NULL) {
		if (left == temp->left && right == temp->right) {
			return 0;
		}
		temp = temp->next;
	}
	return 1;
}

FRW * init_frw(int bottom, int left, int right) {
	FRW *newnode = (FRW *)malloc(sizeof(FRW));
	if (newnode == NULL)
		return (FRW *)NULL;
	
	newnode->bottom = bottom;
	newnode->left 	= left;
	newnode->right	= right;
	newnode->prev	= NULL;
	newnode->next	= NULL;
	return newnode;
}

void insert_frw(FRW *newnode) {
	FRW *temp;
	if (rwhead == NULL) {
		rwhead = newnode;
		rwhead->next = NULL;
		rwhead->prev = NULL;
		return;
	}
	
	temp = rwhead;
	while (temp->next != NULL) {
		if ((temp->bottom == newnode->bottom) &&
			(temp->left	== newnode->left) &&
			(temp->right == newnode->right))
			return;
		temp = temp->next;
	}
	
		if ((temp->bottom == newnode->bottom) &&
			(temp->left	== newnode->left) &&
			(temp->right == newnode->right))
			return;
/* 	if (temp->bottom == newnode->bottom) {
        if (temp->left > newnode->left)
            temp->left = newnode->left;
            
        if (temp->right < newnode->right)
            temp->right = newnode->right;            
    } else {
        if (temp->left < newnode->left)
            newnode->left = temp->left;
    
        if (temp->right > newnode->right)
            newnode->right = temp->right;
 */
    	temp->next 		= newnode;
	    newnode->prev	= temp;
//    }
}

void print_frwlist(FRW *head) {
	FRW *temp = head;
	printf("---------------\n");
	printf("FRW List contains\n");
	printf("---------------\n");
	while (temp != NULL) {
		printf("bottom:%d \tleft:%d \tright:%d\n", temp->bottom, temp->left, temp->right);
		temp = temp->next;
	}
}

void create_frw(int bottom, int left, int right) {
	FRW *rw		= NULL;
//	printf("create_frw %d %d %d\n", bottom, left, right);
	if (left >= right) { return; }

	rw = init_frw(bottom, left, right);
	insert_frw(rw);
//	print_frwlist(rwhead);
}

void oe_process1(E_Node **oe, int height, F_List *rwll) {
/* 	FRW *temp = rwll->head; */
    FRW *temp = NULL;
	temp = rwhead;
	int right = 0, left = 0;
	int update = 0;

	while ((*oe) != NULL && (*oe)->height == height) {
        update = 0;
        temp = rwhead;
        left = (*oe)->x_left;
        right = (*oe)->x_right;
        if (temp == NULL) {
            create_frw(height, left, right);
        } else {
            while (temp != NULL && !update) {
                if (temp->bottom == height) {
                    if (temp->right >= left && temp->left > (*oe)->x_left)
                        temp->left = (*oe)->x_left;
            
                    if (temp->left <= right && temp->right < (*oe)->x_right)
                        temp->right = (*oe)->x_right;      
                        
                    if (temp->prev != NULL) {
                        if (temp->prev->left <= temp->right) 
                            temp->right = temp->prev->right;
                            
//                        if (temp->prev->right >= temp->left)
//                            temp->left = temp->prev->left;
                    }
                          
                    update = 1;
                } else {
                    if (temp->right >= left && temp->left < (*oe)->x_left)
                        left = temp->left;
    
                    if (temp->left <= right && temp->right > (*oe)->x_right)
                        right = temp->right;
                }
                temp = temp->next;
            }
            if (!update) 
                create_frw(height, left, right);
        }
/* 		while (temp != NULL) {
            if (temp->bottom == height) {
	   		    if (temp->left == (*oe)->x_right) {
				    right 	= temp->right;
			    }
			    if (temp->right == (*oe)->x_left) {
				    left 	= temp->left;
			    }
            }
			temp 	= temp->next;
		}
		if (right < (*oe)->x_right) {
			right = (*oe)->x_right;
		}
		if (left > (*oe)->x_left) {
			left = (*oe)->x_left;
		}
*/
// 		create_frw(height, left, right);
//		create_frw(height, (*oe)->x_left, (*oe)->x_right);
		(*oe) = (*oe)->next;
	}
}

void oe_process(E_Node **oe, int height, F_List *rwll) {
    FRW *temp = NULL;
	int right = 0, left = 0;
	int update = 0;

	while ((*oe) != NULL && (*oe)->height == height) {
        update = 0;
        temp = rwhead;
        left = (*oe)->x_left;
        right = (*oe)->x_right;
        if (temp == NULL) {
            create_frw(height, left, right);
        } else {
            while (temp != NULL && !update) {
                if (temp->left == (*oe)->x_right) {
                    right = temp->right;
                }
                if (temp->right == (*oe)->x_left) {
                    left = temp->left;
                }
                if (temp->bottom == height) {
                    if (temp->right == (*oe)->x_left) {
                        temp->right = right;
                        update = 1;
                    }
                    if ((temp->left == (*oe)->x_right)) {
                        temp->left = left;
                        update = 1;
                    }
                }
                temp = temp->next;
            }
            if (!update) {
                create_frw(height, left, right);
            }
        }
		(*oe) = (*oe)->next;
	}
}

void ie_process(E_Node **ie, int height, F_List *rwll, M_List *merll) {
	FRW *temp = rwll->head, *prev;

	while ((*ie) != NULL && (*ie)->height == height) {
		temp = rwhead;
		if (temp == NULL) {
		    printf("h:%d l:%d r%d\n",(*ie)->height, (*ie)->x_left, (*ie)->x_right);
			printf("something wrong in ie_process!!!\n");
			exit(-1);
		}
		while (temp != NULL) {
			if (
				(temp->right > (*ie)->x_left) && 
				(temp->left < (*ie)->x_right)
			) {
				if (temp == rwhead) {
					rwhead = rwhead->next;
					if (temp->next != NULL)
						temp->next->prev = rwhead;
				} else {
					prev->next = temp->next;
					if (temp->next != NULL)
						temp->next->prev = prev;				
				}

				create_mer(temp, height, merll);

				if (temp->right > (*ie)->x_left && check_frw(temp->left, (*ie)->x_left, rwll)) {
					create_frw(temp->bottom, temp->left, (*ie)->x_left);
				}

				if (temp->left < (*ie)->x_right && check_frw((*ie)->x_right, temp->right, rwll)) {
					create_frw(temp->bottom, (*ie)->x_right, temp->right);
				}				
			} else {
				prev = temp;
			}
			temp = temp->next;
		}
		(*ie) = (*ie)->next;
	}
}

M_List * fs_algorithm(G_Node *ge, E_Node *ie, E_Node *oe) {
	F_List *rwll	= (F_List *) NULL;
	M_List *merll	= NULL;

	rwll	= (F_List *)malloc(sizeof(F_List));
	merll	= (M_List *)malloc(sizeof(M_List));
	merll->head = NULL;

	while (ge != NULL) {
		if (ge->oe_count >= 1) {
//			printf("out %d\n", ge->oe_count);
			printf("fs_algorithm: out-edge process\n");
//			create_frw(ge->height, 0, MAX_WIDTH);
			oe_process(&oe, ge->height, rwll);
		print_frwlist(rwhead);
		}
		if (ge->ie_count >= 1) {
//			printf("in  %d\n", ge->ie_count);
			printf("fs_algorithm: in-edge process\n");
			ie_process(&ie, ge->height, rwll, merll);
		print_frwlist(rwhead);
		}
		ge = ge->next;
	}
	free(rwll);
	return merll;
}

G_Node * init_gnode(int height, int ie_count, int oe_count) {
	G_Node *newnode 	= (G_Node *)malloc(sizeof(G_Node));
	if (newnode == NULL)
		return (G_Node *) NULL;

	newnode->height 	= height;
	newnode->ie_count	= ie_count;
	newnode->oe_count	= oe_count;
	newnode->prev		= NULL;
	newnode->next		= NULL;
	return newnode;
}

void insert_gnode(G_Node *newnode) {
	G_Node *temp, *prev;
	if (ghead == NULL) {
//        printf("insert_gnode: Empty head\n");
		ghead = newnode;
		ghead->next = NULL;
		ghead->prev = NULL;
		return;
	}
	
	temp = ghead;
	while (temp->height < newnode->height) {
		prev = temp;
		temp = temp->next;
		if (temp == NULL)
			break;
	}
	
	if (temp == NULL) {
//        printf("insert_gnode: insert tail\n");
		prev->next 		= newnode;
		newnode->prev	= prev;
		return;
	}
	
	if (temp->height == newnode->height) {
		temp->ie_count += newnode->ie_count;
		temp->oe_count += newnode->oe_count;
	} else {
		if (temp == ghead) {
			newnode->next 	= ghead;
			ghead 			= newnode;
		} else {
			prev->next 		= newnode;
			newnode->prev	= prev;
			newnode->next 	= temp;
			temp->prev 		= newnode;
		}
	}
}

void delete_gnode(G_Node *node, char type) {
	G_Node *temp, *prev;
	
	temp = ghead;
	while (node->height != temp->height) {
		prev = temp;
		temp = temp->next;
		if (temp == NULL) {
			printf("error: delete_gnode: Node not found\n");
			return;
		}
	}
	
	if (type == 'i')
		temp->ie_count--;
	else
		temp->oe_count--;
		
	if (temp->ie_count > 0 || temp->oe_count > 0)
		return;
		
	if (temp == ghead) {
		ghead = temp->next;
		ghead->prev = NULL;
	} else {
		prev->next = temp->next;
		if (temp->next != NULL)
			temp->next->prev = prev;
	}
	free(temp);
}

void print_glist(G_Node *head) {
	G_Node *temp = head;
	printf("---------------\n");
	printf("G List contains\n");
	printf("---------------\n");
	while (temp != NULL) {
		printf("height:%d \tin_counter:%d out_counter:%d\n", temp->height, temp->ie_count, temp->oe_count);
		temp = temp->next;
	}
}

E_Node * init_enode(int height, int x_left, int x_right, G_Node *gnode) {
	E_Node *newnode	= (E_Node *)malloc(sizeof(E_Node));
	if (newnode == NULL)
		return (E_Node*) NULL;
	
	newnode->height		= height;
	newnode->x_left		= x_left;
	newnode->x_right	= x_right;
	newnode->gnode		= gnode;
	newnode->prev		= NULL;
	newnode->next		= NULL;
	return newnode;
}

void insert_enode(E_Node *newnode, char type) {
//    printf("insert_enode %d %d %d\n", newnode->height, newnode->x_left, newnode->x_right);
	E_Node *temp, *prev;
	E_Node *ehead;
	if (type == 'i')
		ehead = iehead;
	else
		ehead = oehead;
		
	if (ehead == NULL) {
//        printf("insert_enode: insert head %d %d %d\n", newnode->height, newnode->x_left, newnode->x_right);
		ehead = newnode;
		ehead->next = NULL;
		ehead->prev = NULL;
		if (type == 'i')
			iehead = ehead;
		else
			oehead = ehead;
		return;
	}
	
	temp = ehead;
	while (temp->height <= newnode->height) {
		prev = temp;
		temp = temp->next;
		if (temp == NULL)
			break;
	}
	
	if (temp == NULL) {
//        printf("insert_enode: insert tail %d %d %d\n", newnode->height, newnode->x_left, newnode->x_right);
		prev->next 		= newnode;
		newnode->prev	= prev;
		if (type == 'i')
			iehead = ehead;
		else
			oehead = ehead;
		return;
	}
	
	if (temp == ehead) {
		newnode->next 	= ehead;
		ehead 			= newnode;
	} else {
		prev->next 		= newnode;
		newnode->prev	= prev;
		newnode->next 	= temp;
		temp->prev 		= newnode;
	}
	
	if (type == 'i')
		iehead = ehead;
	else
		oehead = ehead;
}

void delete_enode(E_Node *node, char type) {
	E_Node *temp, *prev;
	E_Node *ehead;
	if (type == 'i')
		ehead = iehead;
	else
		ehead = oehead;

	if (ehead == NULL) {
		printf("error: delete_enode: list is empty\n");
		return;
	}
	
	temp = ehead;
	while (temp != node) {
		prev = temp;
		temp = temp->next;
		if (temp == NULL) {
			printf("error: delete_enode: delete node not found\n");
			exit(-1);
			return;
		}
	}
	if (temp == ehead) {
		ehead = temp->next;
		ehead->prev = NULL;
		if (type == 'i') {
			iehead = ehead;
			delete_gnode(temp->gnode, 'i');
		} else {
			oehead = ehead;
			delete_gnode(temp->gnode, 'o');
		}
	} else {
		prev->next = temp->next;
		if (temp->next != NULL)
			temp->next->prev = prev;
		if (type == 'i') {
			delete_gnode(temp->gnode, 'i');
		} else {
			delete_gnode(temp->gnode, 'o');
		}		
	}
	free(temp);
}

void print_elist(E_Node *head) {
	E_Node *temp = head;
	printf("---------------\n");
	printf("E List contains\n");
	printf("---------------\n");
	while (temp != NULL) {
		printf("height:%d \tx_left:%d \tx_right:%d\n", temp->height, temp->x_left, temp->x_right);
		temp = temp->next;
	}
}
